package com.lishem.carl._07tree;

import com.lishem.common.TreeNode;

/**
 * https://leetcode.cn/problems/maximum-binary-tree/description/
 * <p>
 * 给定一个不重复的整数数组 nums 。 最大二叉树可以用下面的算法从nums递归地构建:
 * <p>
 * 创建一个根节点，其值为nums中的最大值。
 * <p>
 * 递归地在最大值左边的子数组前缀上构建左子树。
 * <p>
 * 递归地在最大值右边的子数组后缀上构建右子树。
 * <p>
 * 返回 nums 构建的 最大二叉树 。
 */
public class _24LetCode654_最大二叉树 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int left, int right) {
        if (right < left) {
            return null;
        }
        int maxIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[maxIndex] < nums[i]) {
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = buildTree(nums, left, maxIndex - 1);
        root.right = buildTree(nums, maxIndex + 1, right);
        return root;
    }

    public static void main(String[] args) {
        _24LetCode654_最大二叉树 sol = new _24LetCode654_最大二叉树();
        TreeNode treeNode1 = sol.constructMaximumBinaryTree(new int[]{3, 2, 1});
        TreeNode treeNode2 = sol.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
    }

}
